#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define swap(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

#define SIZE    80000

int myArray[SIZE];

void printSorted(int array[])
{
    int i;
    for( i = 0; i < SIZE; i++){
        printf("%d\n", array[i]);
    }
}

void init()
{
    int i;
    for( i = 0; i < SIZE; i++){
        myArray[i] = rand()%1000000;
    }
    // printSorted(myArray);
}

//Bubble sort
void bubblesort(int array[], int len)
{
    int i,j,temp;
    for(i=0;i<len;i++)
    {
        for(j=0;j<len-1;j++)
        {
            if(array[j+1]<array[j])
                swap(array[j],array[j+1],temp);
        }
    }
}

//Insertion sort
void insertionsort(int array[],int len)
{
    int i = 1,j,temp;
    while (i < len){
        j = i;
        while(j > 0 && array[j-1] > array[j]){
            swap(array[j],array[j-1],temp);
            j = j - 1;
        }
        i = i + 1;
    }
}

//selection sort
void selectionsort(int array[],int len)
{
    int i = 0,temp;
    while (i < len){
        int j = i + 1;
        int minpos = i;
        while (j < len){
            if (array[j] < array[minpos]){
                minpos = j;
            }
            j = j + 1;
        }
        swap(array[i],array[minpos],temp);
        i = i + 1;
    }
}

//Shell sort
void shellsort(int array[],int len)
{
    int i,key,j,temp;
    int gap = len / 2;
    while (gap > 0){
        for(i = gap; i < len; i++){
            key = array[i];
            j = i;
            while(j>=gap&&array[j-gap]>key){
                swap(array[j-gap],array[j],temp);
                j -= gap;
            }
            array[j] = key;
        }
        gap /= 2;
    }
}

void move_down(int array[], int root, int len){
    int temp, last = len - 1;
    while(1){
        int left = 2 * root + 1;
        if (left > last){
            break;
        }
        int right = left + 1;
        int child = (right <= last && array[right] > array[left])?right:left;
        if (array[child] > array[root]){
            swap(array[root], array[child],temp);
        }
        root = child;
    }
}

//Heap sort
void heap_sort(int array[], int len){
    int i,temp;
    if (len <= 1)
        return;
    
    int last_parent = (len - 2) / 2;
    for (i = last_parent; i >= 0; i--){
        move_down(array, i, len);
    }
    for (i = len-1; i >= 1; i--){
        swap(array[0],array[i], temp);
        move_down(array, 0, i);
    }
}

//Main 
int main()
{
    double elapsed_T;
    clock_t  begin, end;

    srand(0);
    init();

    int bubble[SIZE];
    memcpy(bubble, myArray, sizeof(bubble));
    begin=clock();
    bubblesort(bubble,SIZE);
    end=clock();
    elapsed_T=(((double)(end-begin))/CLOCKS_PER_SEC);
    printf("Time taken by bubble sort is");
    printf(" %0.5lf\tsecs\n",elapsed_T);


    int insertion[SIZE];
    memcpy(insertion, myArray, sizeof(insertion));
    begin=clock();
    insertionsort(insertion,SIZE);
    end=clock();
    elapsed_T=(((double)(end-begin))/CLOCKS_PER_SEC);
    printf("Time taken by insertion sort is");
    printf(" %0.5lf \tsecs\n",elapsed_T);


    int selection[SIZE];
    memcpy(selection, myArray, sizeof(selection));
    begin=clock();
    selectionsort(selection,SIZE);
    end=clock();
    elapsed_T=(((double)(end-begin))/CLOCKS_PER_SEC);
    printf("Time taken by selection sort is");
    printf(" %0.5lf \tsecs\n",elapsed_T);

    int shell[SIZE];
    memcpy(shell, myArray, sizeof(shell));
    begin=clock();
    shellsort(shell,SIZE);
    end=clock();
    elapsed_T=(((double)(end-begin))/CLOCKS_PER_SEC);
    printf("Time taken by shell sort is");
    printf(" %0.5lf \tsecs\n",elapsed_T);
   
    int heap[SIZE];
    memcpy(heap, myArray, sizeof(heap));
    begin=clock();
    heap_sort(heap,SIZE);
    end=clock();
    elapsed_T=(((double)(end-begin))/CLOCKS_PER_SEC);
    printf("Time taken by heap sort is");
    printf(" %0.5lf \tsecs\n",elapsed_T);

    return 0;
}